/**
 * 30.串联所有单词的子串
 * 
 * 给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
 * 注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
 * 
 * 示例 1：
 * 输入：
 * s = "barfoothefoobarman",
 * words = ["foo","bar"]
 * 输出：[0,9]
 * 解释：
 * 从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
 * 输出的顺序不重要, [9,0] 也是有效答案。
 * 
 * 示例 2：
 * 输入：
 * s = "wordgoodgoodgoodbestword",
 * words = ["word","good","best","word"]
 * 输出：[]
 */
package zw;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

class T30 {
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if(words == null || words.length == 0) {
            return result;
        }
        int size = words.length;
        int wordsLength = words[0].length();
        HashMap<String, Integer> wordsMap = new HashMap<>();
        for (String word : words) {
            if (wordsMap.containsKey(word)) {
                wordsMap.put(word, wordsMap.get(word) + 1);
            } else {
                wordsMap.put(word, 1);
            }
        }

        for (int i = 0; i + size * wordsLength <= s.length(); i++) {
            HashMap<String, Integer> tempMap = new HashMap<>();
            for (int j = 0; j < size; j++) {
                String temp = s.substring(i + j * wordsLength, i + j * wordsLength + wordsLength);
                if (wordsMap.containsKey(temp)) {
                    if (!tempMap.containsKey(temp)) {
                        tempMap.put(temp, 1);
                    } else if (tempMap.get(temp).equals(wordsMap.get(temp))) {
                        break;
                    } else {
                        tempMap.put(temp, tempMap.get(temp) + 1);
                    }
                } else {
                    break;
                }
                if (j == size - 1) {
                    result.add(i);
                }
            }
        }
        return result;
    }

    public static List<Integer> findSubstring2(String s, String[] words) {
        int wordLen = words[0].length();
        HashMap<String, Integer> wordMap = new HashMap<>();
        for(String str : words) {
            int value = wordMap.getOrDefault(str, 0);
            wordMap.put(str, value+1);
        }
        List<Integer> result = new ArrayList<>();
        int size = words.length;
        for(int i = 0; i < wordLen; i++) {
            HashMap<String, Integer> tempMap = new HashMap<>();
            int num = 0;
            for(int j = 0; i+j+wordLen <= s.length(); ){
                String str = s.substring(i+j, i+j+wordLen);
                if(wordMap.getOrDefault(str, 0) > 0) {
                    if(wordMap.get(str) >= tempMap.getOrDefault(str, 0)+1) {
                        tempMap.put(str, tempMap.getOrDefault(str, 0)+1);
                        num++;
                        // 完全匹配
                        if(num == words.length) {
                            result.add(i+j-wordLen*size+wordLen);
                            String firstStr = s.substring(i+j-wordLen*(size-1), i+j-wordLen*(size-1)+wordLen);
                            tempMap.put(firstStr, tempMap.get(firstStr)-1);
                            num--;
                        }
                        j += wordLen;
                    } else { // 匹配数量超出
                        String firstStr = s.substring(i+j-wordLen*num, i+j-wordLen*(num-1));
                        while(!firstStr.equals(str)){
                            tempMap.put(firstStr, tempMap.get(firstStr)-1);
                            num--;
                            firstStr = s.substring(i+j-wordLen*num, i+j-wordLen*(num-1));
                        }
                        tempMap.put(str, tempMap.get(str)-1);
                        num--;
                    }
                } else {  // 字符串不存在
                    tempMap.clear();
                    num = 0;
                    j += wordLen;
                }
            }
        }
        return result;
    }
}
